#include "./ActiveEdgeTable.h"
#include <stdio.h>

// declaration so can use in drawPolygon(); is there a way around this?
//    perhaps move all of the extra functions (or those needed) into here?
void setFramebuffer(int x, int y, float R, float G, float B);
bool PointCompare(Point* p1, Point* p2);
bool clip(Point* l1, Point* l2, Point c1, Point c2);
double intersection(Point p1, Point p2, Point p3, Point p4);
Point corner(Point p1, Point p2, Point p3, Point p4);




/***********************************  Point  ******************************************/


bool PointCompare(Point* p1, Point* p2)
{
	return ((p1->x == p2->x) && (p1->y == p2->y));
}






/***********************************  Edge  ******************************************/

Edge::Edge(Point _p1, Point _p2)
{
	double slope;

//	conclusion: using these stores makes no difference to drawPolygon() (which does still have problems)
	p1 = _p1;		// Maybe should just use these; think about it
	p2 = _p2;		//
	
	// Can alter this to use the ? operator, but for clarity, will use if/then for now
	if(_p1.y > _p2.y)	// _p1 is the higher y value (lower placed) point
	{
		// does the order matter?
//		p1 = _p1;	// lower placed point
//		p2 = _p2;	// higher placed point

		printf("Cap'n!:\t_p2 < _p1\n_p2:\t%d,%d\t_p1:\t%d,%d\n",_p2.x,_p2.y,_p1.x,_p1.y);
		maxY = (int)_p1.y;	// do want to keep minY, maxY as ints
		minY = (int)_p2.y;
		currentX = _p2.x;

		slope = ((double)_p1.y - (double)_p2.y)/((double)_p1.x - (double)_p2.x);	// (y2-y1)/(x2-x1)
		xIncr = 1/slope;
	
		printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
		p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);


	}
	else if(_p2.y > _p1.y)	// _p2 is the higher y value (lower placed) point
	{
//		p1 = _p2;	// lower placed point
//		p2 = _p1;	// higher placed point

		printf("Cap'n!:\t_12 < _21\n_p1:\t%d,%d\t_p2:\t%d,%d\n",_p1.x,_p1.y,_p2.x,_p2.y);
		maxY = (int)_p2.y;	// do want to keep minY, maxY as ints
		minY = (int)_p1.y;
		currentX = _p1.x;
		
		slope = ((double)_p2.y - (double)_p1.y)/((double)_p2.x - (double)_p1.x);	// (y2-y1)/(x2-x1)
		xIncr = 1/slope;

		
		printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
		p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);
	}
	else	// horizontal!  Choose _p1 to be max (though think it should actually just ignore this edge?)
	{
		printf("Cap'n!:\t_p1 = _p2\n");
		// do nothing
	}	
}


Edge::~Edge()  {   }	// nothing needed to implement destructor

/*
bool
Edge::compareEdge(Edge first, Edge second)
{
	if(first.currentX < second.currentX)
		return true;
	else
		return false;
}
*/

bool
Edge::operator<(Edge& rhs)
{
	return (this->currentX < rhs.currentX);
}


void
Edge::printEdge()
{
	printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
		p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);
}


bool
compareEdge(Edge* first, Edge* second)
{
//	printf("first.currentX: %f\tsecond.currentX: %f\t\n", first->currentX, second->currentX);
	if(first->currentX < second->currentX)
		return true;
	else
		return false;
}


/***********************************  EdgeList  ******************************************/
EdgeList::EdgeList(Edge _e)
{
	this->elmaxY = _e.maxY;	// store the scanline value
	this->elminY = _e.minY;
}

EdgeList::EdgeList(Edge* _e)
{
	this->elmaxY = _e->maxY;
	this->elminY = _e->minY;
}

EdgeList::EdgeList()
{
	this->elmaxY = 0;
	this->elmaxY = 0;
	printf("Cap'n!\tDefault constructor called");
}

EdgeList::~EdgeList() { 
	// delete each edge e
}	

/*
void
EdgeList::addEdge(Edge _e)
{
	edgeList.push_back(_e);
//	edgeList.sort( Edge::compareEdge );
	edgeList.sort();	// by currentX
}
*/

void
EdgeList::addEdge(Edge* _e)
{
	edgeList.push_back(_e);
	edgeList.sort();
}


void
EdgeList::printEdgeList()	// for debugging
{
	std::list<Edge*>::iterator elIter;

	// at each edge, print the two points
	for(elIter = edgeList.begin(); elIter != edgeList.end(); elIter++)
		printf("p1:\t%d,%d\tp2:\t%d,%d\n", (*elIter)->p1.x, (*elIter)->p1.y,
			(*elIter)->p2.x, (*elIter)->p2.y);

}




// compares EdgeLists via their "y" value
bool 
EdgeList::compareEdgeList(EdgeList first, EdgeList second)
{
	if(first.elminY < second.elminY)
		return true;
	else
		return false;	
}




bool
EdgeList::operator<(EdgeList& rhs)
{
	return (this->elminY < rhs.elminY);
}



/***********************************  ActiveEdgeList  ******************************************/
/*
ActiveEdgeList::ActiveEdgeList(Edge _e)
{
	EdgeList::EdgeList(_e);
}

ActiveEdgeList::~ActiveEdgeList()
{
	EdgeList::~EdgeList
}

bool 
ActiveEdgeList::operator<(ActiveEdgeList& rhs)	// want to sort by currentX
{
	return
}
*/

/***********************************  Polygon  ******************************************/


Polygon::Polygon(int _windowWidth, int _windowHeight, Color _color) {
	windowWidth = _windowWidth;
	windowHeight = _windowHeight;	
	color = _color;

	// may be more efficient to have it be a list and add entries only when an edge is added at that entry
	//    and just keep a "line identity"
	//aeTable = new std::vector<EdgeList>;	// get a vector of list of Edges of the right size
}


Polygon::~Polygon() { 
	//delete aeTable
	//delete aeList (maybe)	
}

/*
void 
Polygon::addEdge(Edge e)	// called when the user left or right clicks
{
	printf("Regular Polygon::addEdge() called\n");
	std::list<EdgeList>::iterator iter, next;	

	for(iter = aeTable.begin(); iter != aeTable.end(); iter++)
	{
		if((*iter).elminY == e.minY)	// correct EdgeList
		{
			(*iter).addEdge((e));	// add an edge at that point
			return;
		}
	}

	// no correct scanline value was found 
	//    => add a new EdgeList with the correct scanline value
	EdgeList* el = new EdgeList(e);		// new EdgeList
	el->elminY = e.minY;						// considering proper scanline
	el->elmaxY = e.maxY;
	el->addEdge(e);						// add the edge to the EdgeList
	aeTable.push_back(*el);				// stick the EdgeList in the table
//	aeTable.sort(EdgeList::compareEdgeList);		// make sure the table is in order (wrt. y)
	aeTable.sort();
}
*/



void 
Polygon::addEdge(Edge *e)
{
	std::list<EdgeList*>::iterator iter, next;
	Point* t1;
	Point* t2;
	t1 = new Point;
	t2 = new Point;
	t1->x = e->p1.x;
	t1->y = e->p1.y;

	t2->x = e->p2.x;
	t2->y = e->p2.y;

// need it now so that the vertices are ordered
	vTable.push_back(t1);
	vTable.push_back(t2);	// stick the endpoints in the vertex table
	vTable.unique(PointCompare);			// remove any duplicates

	for(iter = aeTable.begin(); iter != aeTable.end(); iter++)
	{
		if((*iter)->elminY == e->minY)	// correct EdgeList
		{
			(*iter)->addEdge(e);	// add an edge at that point
			return;
		}
	}

	// no correct scanline value was found 
	//    => add a new EdgeList with the correct scanline value
	EdgeList* el = new EdgeList(e);		// new EdgeList
	el->elminY = e->minY;						// considering proper scanline
	el->elmaxY = e->maxY;
	el->addEdge(e);						// add the edge to the EdgeList
	aeTable.push_back(el);				// stick the EdgeList in the table
//	aeTable.sort(EdgeList::compareEdgeList);		// make sure the table is in order (wrt. y)
	aeTable.sort();
}





void 
Polygon::drawPolygon()	// will be the one to call setFrameBuffer();
{
	int line = 0;	// current line being drawn
	std::list<EdgeList*>::iterator aeTableIter = aeTable.begin();
	std::list<Edge*>::iterator aeListIter;
	std::list<Edge*>::iterator EdgeListIter;
	

	while( line < windowHeight )
	{
//		printf("beginning:\n");

		// 1. Add edges to Active Edge List from Active Edge Table based on their minimum Y value
		for(aeTableIter = aeTable.begin(); aeTableIter != aeTable.end(); aeTableIter++)
		{
			if((*aeTableIter)->elminY == line)	// there is an entry that starts at this scanline
			{
//				printf("1: checking table\n");
				for(EdgeListIter = (*aeTableIter)->edgeList.begin();		// take that edge list that is valid
					EdgeListIter != (*aeTableIter)->edgeList.end(); EdgeListIter++) // go through it
				{
//					printf("1: found edge\n");
					aeList.addEdge((*EdgeListIter));
//					printf("1: added edge\n");
//					aeList.push_back(*EdgeListIter);	// and add the entries into the Active Edge List
				}
//				printf("1: incrementing...");
//				printf("1: incremented!\n");
			}
		}


//		printf("1 done, ");


		// 2. Remove edges that end at that line
//		for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); aeListIter++)	
		aeListIter = aeList.edgeList.begin();
		while(aeListIter != aeList.edgeList.end())
		{		// traverse the active edge list
			// if an edge ends at this scanline
			if((*aeListIter)->maxY == line)	
			{	// erase the edge
				// erase() returns an iterator to the one after the one that was erased
				if(aeListIter == aeList.edgeList.begin())
				{	// was at the beginning
					aeListIter = aeList.edgeList.erase(aeListIter);	
					aeListIter = aeList.edgeList.begin();	// probably unneeded
					continue;
				}
				else
				{
					aeListIter = aeList.edgeList.erase(aeListIter);	// don't move the iterator
					continue;
				}
//				printf("removed ");
			}
			aeListIter++;
		}



		// If there is nothing in the list, there is nothing to draw and no
		//    reason to go on
		if(aeList.edgeList.empty())	// returns 1 if is empty
		{
			line++;					// go to the next line and try again
//			printf("continuing\n");
			continue;				
		}



//		printf("2 done\n");

		
		// 3. Fill Pixels
		bool inside = false;	// toggle pixels on and off as edges are encountered; default off
		aeList.edgeList.sort(compareEdge);	// sorts by currentX
		
/*
		double test1, test2;
		aeListIter = aeList.edgeList.begin();
		test1 = (*aeListIter)->currentX;
		aeListIter++;
		test2 = (*aeListIter)->currentX;
		printf("Sort test: %f < %f: %d\n", test1, test2, (test1 < test2));
*/
		aeListIter = aeList.edgeList.begin();
		for(int i = 0; i < windowWidth; i++)	// each x coordinate at y = line
		{	
/*
		if(aeList.edgeList.empty())	// error checking; should never happen
			{
				printf("somehow it's empty.. =(\n");
				break;
			}
*/

//			while(aeListIter != aeList.edgeList.end())	// until is past the last edge
			if(aeListIter != aeList.edgeList.end())	// if is past the last edge
			{
		// If aeListITer == ~.~.end(), then it's PAST The last element and at (basically) a footer.
		// Thus, simply break if it's at ~.~.end()

//				printf("break 2\n");
//				break;
//			}
				//if((*aeListIter)->currentX <= i)	// passed an edge (I think this is correct)
				while((*aeListIter)->currentX <= i)	// passed an edge (I think this is correct)
				{
					inside = !inside;			// invert whether you're coloring or not
	//				printf("Row passed an edge:\t");
					aeListIter++;				// check the next edge
					if(aeListIter == aeList.edgeList.end())
						break;
					//continue;	//??

 
	/*				
					else
					{
						printf("break 3\n");
						break;
					}
	*/
				}
			}

			if(inside)						// if inside a polygon
			{
//				printf("+");	// for debugging
				setFramebuffer(i, line, color.r, color.g, color.b);	// color the pixel!
			}
			else
			{
//				printf(".");	// debugging
			}
		}

//		printf("line %d\n", line);
		
//		printf("3 done, ");




		// 4. Increment x-values on edges in Active Edge List
		for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); aeListIter++)	
		{
			(*aeListIter)->currentX += (*aeListIter)->xIncr;	// incrementing x values on all edges
		}	// don't need these braces, but w/e

//		printf("4 done\n");

		// 5. Increment line
		line++;

	}


	// empty the active edge list; should help; doesn't; the shapes are migrating.. what am I changing
	for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); 1)
	{
		printf("potentially stuck in a loop...\n");
		aeListIter = aeList.edgeList.erase(aeListIter);
	}


	// restore the aeTable
	// 1. clear it
	for(aeTableIter = aeTable.begin(); aeTableIter != aeTable.end(); 1)
		aeTableIter = aeTable.erase(aeTableIter);

	// 2. copy the point table, clear it (to avoid endless loop)
	std::list<Point*> temp;
	std::list<Point*>::iterator pIter = vTable.begin();
	while(pIter != vTable.end())
	{
		temp.push_back((*pIter));
		pIter = vTable.erase(pIter);
	}

	// 3. replace it
	Point p1, p2;
	Edge* tempEdge;
	int i = 0;
	pIter = temp.begin();
	while(pIter != temp.end())
	{
		printf("\n%d\n", ++i);
		p1 = (*(*pIter));
		pIter++;
		if(pIter == temp.end())	// done
			break;
		p2 = (*(*pIter));
		tempEdge = new Edge(p1,p2);
		addEdge(tempEdge);
	}

}




Polygon* 
Polygon::clipPolygon(Polygon* old, Point _p1, Point _p2)
{
	Polygon* clipped = new Polygon(windowWidth, windowHeight, color);	// empty polygon
	Point e1, e2, left1, left2;
	bool leftIntersection = false;
	double left;

	if(_p1.x < _p2.x)
		left = _p1.x;
	else
		left = _p2.x;


	if((_p1.x == _p2.x) || (_p1.y == _p2.y))
	{
		printf("clipping along a line\n");
		// clipping on a line is nothing => return nothing
		return clipped;
	}

	// 1. clip each line/edge; save the endpoints;
	//      make sure that points that are out in two directions put a vertex in the corner
	//      if the next edge intersects a different side
	//           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y

	
	std::list<Point*>::iterator pIter = vTable.begin();
//	std::list<Edge*>::iterator elIter = (*aeTable.begin())->edgeList.begin();
	Edge* tempEdge = NULL;
	Edge* tempEdge2 = NULL;	// checking corners
	Edge* tempEdge3 = NULL;
//	Point origin = (*(*pIter));	// first point of the vertex list

	while(pIter != vTable.end())	// while there are vertices remaining
	{
		// copy two points
		e1.x = (*pIter)->x;
		e1.y = (*pIter)->y;

		pIter++;

		if(pIter == vTable.end())
		{	// origin was already at the end; nothing to be done, break out
			break;
		}
		e2.x = (*pIter)->x;
		e2.y = (*pIter)->y;
		
		if((clip(&e1, &e2, _p1, _p2)) == false)	// check to see if point is clipped
			continue;	// if the points didn't intersect an edge, ignore them

		if(e1.x == left)
		{
			if(leftIntersection)
			{
				left2 = e1;
				leftIntersection = false;
				tempEdge3 = tempEdge;
				tempEdge = new Edge(left1, left2);
				clipped->addEdge(tempEdge);
				tempEdge = tempEdge3;
			}
			else
			{
				left1 = e1;
				leftIntersection = true;
			}
		}
		else if(e2.x == left)
		{
			if(leftIntersection)
			{
				left2 = e2;
				leftIntersection = false;
				tempEdge3 = tempEdge;
				tempEdge = new Edge(left1, left2);
				clipped->addEdge(tempEdge);
				tempEdge = tempEdge3;
			}
			else
			{
				left1 = e2;
				leftIntersection = true;
			}
		}

		//      make sure that points that are out in two directions put a vertex in the corner
		//      if the next edge intersects a different side
		//           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y
		tempEdge2 = tempEdge;	// last Edge added; for corner checking
		tempEdge = new Edge(e1,e2);	// new edge

		if(tempEdge2 != NULL)	// corner checking
		{	// i.e. there was an edge before the current
			//if the ys are equal, no edge needed	|| (tempEdge2->p2.y == tempEdge->p1.y))
			if(tempEdge2->p2.x == tempEdge->p1.x)	
			{	// they are clipped along the same rectangle-edge
				tempEdge3 = new Edge(tempEdge2->p2, tempEdge->p1);
				clipped->addEdge(tempEdge3);
			}
			else if (tempEdge2->p2.y != tempEdge->p1.y)	// if they are equal, no slope => no problem
			{	// some intervening corner
				// find the corner
				Point t1 = tempEdge2->p2;
				Point t2 = tempEdge->p1;
				// add an edge from tempEdge2->p2 to corner, and corner to e1
				Point t3 = corner(t1, t2, _p1, _p2);	
				if((t3.x == -1) && (t3.y = -1))
					;	// point not needed
				else
				{
					tempEdge3 = new Edge(t1, t3);
					clipped->addEdge(tempEdge3);
					tempEdge3 = new Edge(t3, t2);
					clipped->addEdge(tempEdge3);
					continue;
				}
			}
		}

		// add the edge
		clipped->addEdge(tempEdge);
	}


	// strangely (and conveniently) enough, the last vertex is in the vTable 
	//    twice; this code is therefore unneeded
/*
	// reusing code to add the last edge
	// add the last edge
	e1 = e2;
	e2 = origin;
	clip(&e1, &e2, _p1, _p2);	// point is clipped

	//      make sure that points that are out in two directions put a vertex in the corner
	//      if the next edge intersects a different side
	//           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y
	tempEdge2 = tempEdge;	// last Edge added; for corner checking
	tempEdge = new Edge(e1,e2);	// new edge

	if(tempEdge2 != NULL)	// corner checking
	{	// i.e. there was an edge before the current
		if((tempEdge2->p2.x == tempEdge->p1.x) || (tempEdge2->p2.y == tempEdge2->p1.x))
		{	// they are clipped along the same rectangle-edge
			tempEdge3 = new Edge(tempEdge2->p2, tempEdge->p1);
			clipped->addEdge(tempEdge3);
		}
		else
		{	// some intervening corner
			// find the corner
			Point t1 = tempEdge2->p2;
			Point t2 = tempEdge->p1;
			// add an edge from tempEdge2->p2 to corner, and corner to e1
			Point t3 = corner(t1, t2, _p1, _p2);	
			tempEdge3 = new Edge(t1, t3);
			clipped->addEdge(tempEdge3);
			tempEdge3 = new Edge(t3, t2);
			clipped->addEdge(tempEdge3);
		}
	}

	// add the edge
	clipped->addEdge(tempEdge);
*/

	// before return, make sure all left-side edges (that originally 
	//    extended past the polygon) are filled in
	// will falter with concave polygons with multiple left intersections
/*	double left;
	if(_p1.x < _p2.x)
		left = _p1.x;
	else
		left = _p2.x;
	bool found_left_edge = false;

	std::list<Edge*>::iterator eListIter;
	std::list<EdgeList*>::iterator aeTableIter;
	for(aeTableIter = clipped->aeTable.begin(); aeTableIter != clipped->aeTable.end(); aeTableIter++)
	{
		eListIter = (*aeTableIter)->edgeList.begin();
		while(eListIter != (*aeTableIter)->edgeList.end())
		{	// go through and find any points that equal left
			if((*eListIter)->p1.x == left)
			{	// save the point
				if(found_left_edge == false)
				{
					e2 = (*eListIter)->p1;
					found_left_edge = true;
				}
				else
				{
					e1 = (*eListIter)->p1;
					tempEdge = new Edge(e1,e2);
					clipped->addEdge(tempEdge);
					found_left_edge = false;
				}
			}
			else if((*eListIter)->p2.x == left)
			{
				if(found_left_edge == false)
				{
					e2 = (*eListIter)->p2;
					found_left_edge = true;
				}
				else
				{
					e1 = (*eListIter)->p2;
					tempEdge = new Edge(e1,e2);
					clipped->addEdge(tempEdge);
					found_left_edge = false;
				}
			}
			eListIter++;
		}
	}
*/	


	return clipped;	// return the address to this clipped polygon
}




void
Polygon::printEdgeTable()
{
	std::list<EdgeList*>::iterator aeTableIter;

	for(aeTableIter = aeTable.begin(); 
		aeTableIter != aeTable.end(); aeTableIter++)
	{
		printf("Edge %d:\n", (*aeTableIter)->elminY);
		(*aeTableIter)->printEdgeList();
	}

	printf("\n");
}




	/***********************************    ******************************************/

// would be more efficient to do this only once
// line endpoint 1, 2 and clipping rectangle corner 1, 2
bool clip(Point* l1, Point* l2, Point c1, Point c2)	
{	// fun linear algebra stuff
//	double tb, tt, tl, tr;	// parameter value of intersection
	double t;				// parameter value of intersection
	Point br, tr, bl, tl;	// edge1, edge2, right bottom, right top, left bottom, left top

	bool intersected = false;	// checking that it actually intersected with the edges


	// will make it easier to manipulate
	if(c1.x > c2.x)	// c1 is right
	{
		if(c1.y > c2.y)	// c1 is bottom-right (in the inverse y coordinates we use)
		{
			br = c1;
			tl = c2;
			
			bl.x = c2.x;
			bl.y = c1.y;

			tr.x = c1.x;
			tr.y = c2.y;
		}
		else	// c1 is top right
		{
			tr = c1;
			bl = c2;

			br.x = c1.x;
			br.y = c2.y;

			tl.x = c2.x;
			tl.y = c1.y;
		}
	}

	else if (c1.x < c2.x)	// c1 is left
	{
		if(c1.y > c2.y)	// c1 is bottom left
		{
			bl = c1;
			tr = c2;

			tl.x = c1.x;
			tl.y = c2.y;

			br.x = c2.x;
			br.y = c1.y;
		}
		else				// c1 is top left
		{
			tl = c1;
			br = c2;

			tr.x = c2.x;
			tr.y = c1.y;

			bl.x = c1.x;
			bl.y = c2.y;
		}
	}

	// left
	t = intersection((*l1), (*l2), bl, tl);
	if((t >= 0.0) && (t <= 1.0))	
	{	// it intersects left edge
		if(l1->x < l2->x)	// from outside inward
		{	// mess only with l1; l2 is inside
			l1->x = l1->x + (l2->x - l1->x)*t;
			l1->y = l1->y + (l2->y - l1->y)*t;
		}
		else	// from inside outward
		{	// l1 is fine; mess with l2
			l2->x = l1->x + (l2->x - l1->x)*t;
			l2->y = l1->y + (l2->y - l1->y)*t;
		}
	}

	// right
	t = intersection((*l1), (*l2), br, tr);
	if((t >= 0.0) && (t <= 1.0))	
	{	// it intersects right edge
		if(l1->x < l2->x)	// from inside outward
		{	// mess only with l2; l1 is inside
			l2->x = l1->x + (l2->x - l1->x)*t;
			l2->y = l1->y + (l2->y - l1->y)*t;
		}
		else	// from outside inward
		{	// l2 is inside; mess with l1
			l1->x = l1->x + (l2->x - l1->x)*t;
			l1->y = l1->y + (l2->y - l1->y)*t;
		}
	}

	// top
	t = intersection((*l1), (*l2), tl, tr);
	if((t >= 0.0) && (t <= 1.0))	
	{	// it intersects top edge
		if(l1->y < l2->y)	// from outside inward
		{	// l2 is inside; mess with l1
			l1->x = l1->x + (l2->x - l1->x)*t;
			l1->y = l1->y + (l2->y - l1->y)*t;
		}
		else	// from outside inward
		{	// l1 is inside; mess with l2
			l2->x = l1->x + (l2->x - l1->x)*t;
			l2->y = l1->y + (l2->y - l1->y)*t;
		}
	}

	// bottom
	t = intersection((*l1), (*l2), bl, br);
	if((t >= 0.0) && (t <= 1.0))	
	{	// it intersects bottom edge
		if(l1->y < l2->y)	// from inside outward
		{	// mess only with l2; l1 is inside
			l2->x = l1->x + (l2->x - l1->x)*t;
			l2->y = l1->y + (l2->y - l1->y)*t;
		}
		else	// from outside inward
		{	// l2 is inside; mess with l1
			l1->x = l1->x + (l2->x - l1->x)*t;
			l1->y = l1->y + (l2->y - l1->y)*t;
		}
	}

	// in case the points were inside; non-intuitional comparisons from inverted y coordinates
	if((l1->x <= br.x) && (l1->x >= bl.x) && (l1->y <= br.y) && (l1->y >= tr.y)
		&& (l2->x <= br.x) && (l2->x >= bl.x) && (l2->y <= br.y) && (l2->y >= tr.y))
		intersected = true;	// perhaps a poor variable name


	return intersected;

	// done
}

double intersection(Point p1, Point p2, Point p3, Point p4)
{	// derived from intersecting parameterized general line equations
	double x0, x1, x2, x3, y0, y1, y2, y3;	// so can easily match derived equation
	double temp1, temp2;

	x0 = p1.x;
	x1 = p2.x;
	x2 = p3.x;
	x3 = p4.x;

	y0 = p1.y;
	y1 = p2.y;
	y2 = p3.y;
	y3 = p4.y;

	temp1 = ((x2-x0)*(y2-y3) - (x2-x3)*(y2-y0));
	temp2 = ((x1-x0)*(y2-y3) - (x2-x3)*(y1-y0));

	return (temp1/temp2);
}

Point corner(Point p1, Point p2, Point c1, Point c2)
{
	// fun linear algebra stuff
	Point br, tr, bl, tl;	// edge1, edge2, right bottom, right top, left bottom, left top
	Point not_needed;	// for when an extra edge isn't needed (some logic problems may preclude 
	not_needed.x = -1;	//    this being necessary
	not_needed.y = -1;

	// will make it easier to manipulate
	if(c1.x > c2.x)	// c1 is right
	{
		if(c1.y > c2.y)	// c1 is bottom-right (in the inverse y coordinates we use)
		{
			br = c1;
			tl = c2;
			
			bl.x = c2.x;
			bl.y = c1.y;

			tr.x = c1.x;
			tr.y = c2.y;
		}
		else	// c1 is top right
		{
			tr = c1;
			bl = c2;

			br.x = c1.x;
			br.y = c2.y;

			tl.x = c2.x;
			tl.y = c1.y;
		}
	}

	else if (c1.x < c2.x)	// c1 is left
	{
		if(c1.y > c2.y)	// c1 is bottom left
		{
			bl = c1;
			tr = c2;

			tl.x = c1.x;
			tl.y = c2.y;

			br.x = c2.x;
			br.y = c1.y;
		}
		else				// c1 is top left
		{
			tl = c1;
			br = c2;

			tr.x = c2.x;
			tr.y = c1.y;

			bl.x = c1.x;
			bl.y = c2.y;
		}
	}

	if(p1.x > p2.x)
	{
		if(p1.y > p2.y)	// either bottom left or top right
		{
			if(p1.x == tr.x)	// is top right
				return not_needed;	//tr;
			else
				return bl;
		}
		else	// p1.y < p2.y
		{	// either top left or bottom right
			if(p1.x == br.x)
				return tl;
			else
				return not_needed;	//br;
		}
	}
	else	// p1.x < p2.x
	{
		if(p1.y > p2.y)
		{	// either top left or bottom right
			if(p1.x == tl.x)
				return tl;
			else
				return not_needed;	//br;
		}
		else	// p1.y < p2.y
		{	// either top right or bottom left
			if(p1.x == bl.x)
				return bl;
			else
				return not_needed;	//tr;
		}
	}
}
